package letcode.oneQuestionPerDay._202004._22;

import letcode.util.TreeNode;

import java.util.*;

/**
 * @Description: 二叉树的右视图
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class TwoTreeRightLook {

    public static void main(String[] args) {
        TreeNode head=new TreeNode(1);
        head.left=new TreeNode(2);
        head.right=new TreeNode(3);
        head.left.right=new TreeNode(5);
        head.right.right=new TreeNode(4);

        System.out.println(rightSideView(head));
    }

    //提供方法      借鉴：层序遍历取最右边的值
    public static List<Integer> rightSideView(TreeNode root) {

        if (root==null)
            return new ArrayList<>();

        List<Integer> ans=new ArrayList<>();
        //队列。存放每层的节点
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //临时数组来存放每一层的节点
            List<Integer> temp=new ArrayList<>();

            int len= queue.size();

            for (int i = 0; i < len; i++) {
                //定义node接收出队节点，
                TreeNode node=queue.poll();
                temp.add(node.val);
                if (node.left!=null)
                    queue.add(node.left);
                if (node.right!=null)
                    queue.add(node.right);
            }
            ans.add(temp.get(temp.size()-1));
        }

         return ans;
    }
}
/*

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
   \
    5           <---
通过次数26,414提交次数41,125
 */